package O4_Insertion_Sort;

import util.SortTestHelper;

/**
 * Created by Choisaaaa on 2018/6/19.
 * 插入排序
 */
public class InsertionSort {
    public static void sort(Comparable[] arr){
        int n = arr.length;
        //以为一个元素不用比较所以从1开始
        for(int i = 1 ;i < n; i++){
            for(int j = i; j > 0 && arr[j].compareTo(arr[j-1]) < 0; j--){
                swap(arr,j,j-1);
            }
        }
    }

    private static void swap(Object[] arr, int j, int i) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t ;
    }

    public static void main(String[] args) {
        int N = 20000;
        Integer[] arr = SortTestHelper.generateRandomArray(N,0,10000);
        SortTestHelper.testSort("O4_Insertion_Sort.InsertionSort",arr);
    }
}
